Міністерство освіти і науки України Національний університет «Львівська політехніка» Інститут комп’ютерних наук та інформаційних технологій
МЕТОДИЧНІ ВКАЗІВКИ до лабораторної роботи № 6 “ГРАДІЄНТНИЙ МЕТОД ЧИСЛОВОЇ ОПТИМІЗАЦІЇ ” з дисциплін “Математичні методи дослідження операцій” і “Методи оптимізації та дослідження операцій” для студентів базових напрямків “Комп’ютерні науки” та “Легка промисловість” стаціонарної і заочної форм навчання Затверджено на засіданні кафедри автоматизованих систем управління Протокол № 6 від 13 листопада 2008 року Львів – 2008 Методичні вказівки до лабораторної роботи № 6 з дисциплін “Математичні методи дослідження операцій” та “Методи оптимізації та дослідження операцій” для студентів базових напрямків “Комп’ютерні науки” і “Легка промисловість” стаціонарної і заочної форм навчання / Укл. Я.П. Романчук, А.М. Ковальчук. – Львів: Видавництво національного університету “Львівська політехніка”, 2003. – 8 с. Укладачі: Романчук Я.П., кад. фіз.-мат. наук, доц. Ковальчук А.М., ст. викладач. Відповідальна за випуск: Шпак З.Я. Рецензент: Вальковський В.О., д-р техн. наук, проф. ЛАБОРАТОРНА РОБОТА № 6 Тема: Градієнтний метод числової оптимізації. Мета роботи: Навчитися знаходити точку оптимуму функції багатьох змінних на основі використання ітераційного градієнтного методу. Завдання: Для вказаного індивідуального завдання побудувати блок-схему (алгоритм), реалізувати його на одній з мов програмування та відшукати оптимальний розв’язок задачі. КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ Лабораторна робота базується на лекційному матеріалі з курсів “Математичні методи дослідження операцій” (ММДО) і “Методи оптимізації та дослідження операцій” (МОДО), задачах, методах і алгоритмах, наведених у відповідних збірниках і довідниках. Градієнтні методи належать до наближених числових методів розв’язування задач нелінійного програмування, оскільки дають точний розв’язок за нескінченне і лише в окремих випадках за скінченне число кроків. З їх використанням можна розв’язувати будь-яку задачу нелінійного програмування, знаходячи, як правило, лише локальний екстремум. Тому застосування цих методів дає найбільший ефект для розв’язування задач випуклого програмування, де локальний екстремум є одночасно і глобальним. Розглянемо задачу максимізації функції f(х), коли обмеження на область зміни змінної х відсутні. Пошук екстремального значення функції f(х) можна починати з будь-якого допустимого розв’язку, наприклад, з точки хk = (x1k; ...; хпk). Градієнтом f(x) функції f(х) в точці хk називається вектор, координатами якого є значення в цій точці частинних похідних першого порядку відповідної змінної, тобто EMBED Equation.3
 Градієнт функції в цій точці вказує напрямок найшвидшого зростання функції f (х). Переміщення з точки хk вздовж градієнту в нову точку хk+1 відбувається по прямій, рівняння якої EMBED Equation.3
. (1) де k – числовий параметр, від величини якого залежить довжина кроку переміщення EMBED Equation.3
. Величина k, при якій досягається найбільший приріст функції, може бути визначена з необхідної умови екстремуму функції ...